package chapter22;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 基本图算法-广度优先遍历
 * <p>
 * 先遍历相邻节点
 */
public class BFS {

    public static void bfs(Node[] G, Node s) {
        s.color = Node.GRAY;
        s.d = 0;
        s.p = null;
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(s);
        while (!queue.isEmpty()) {
            Node u = queue.poll();
            System.out.println("u->" + u.key);
            // 遍历u相邻边的v
            Node next = u;
            while (next != null) {
                Node v = G[next.key];
                if (v.color == Node.WHILE) {
                    v.color = Node.GRAY;
                    v.d = u.d + 1;
                    v.p = u;
                    queue.add(v);
                }
                next = next.next;
            }
            u.color = Node.BLACK;
        }
    }
}
